package sort;

/**
 * @Author: LDeng
 * @Date: 2021-03-29 17:04
 */
public class RedixSort extends Sort<Integer> {

    @Override
    protected void sort() {
        //找到最大值
        int max = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] > max) {
                max = array[i];
            }
        }
        for (int div = 1; div <= max; div = div * 10) {
            countingSort(div);
        }
        //个位数 array[i]/1     %10
        //十位数 array[i]/10  %10
        //百位数 array[i]/100 %10
        //千位数 array[i]/1000%10
        // ...


    }


    protected void countingSort(int div) {
        int[] counts = new int[10];
        //统计每个整数出现的次数，不累加
        for (int i = 0; i < array.length; i++) {
            counts[(array[i] / div) % 10]++;
        }
        //累加次数， 索引-1的值 加上自己的值的，覆盖自己的值
        //得到累加次数的数组
        for (int i = 1; i < counts.length; i++) {
            counts[i] = counts[i - 1] + counts[i];
        }
        //从后往前遍历array元素， 将它放到有序数组中的合适位置
        int[] newArray = new int[array.length];
        for (int i = array.length - 1; i >= 0; i--) {
            //将遍历到的数字放到新数组的counts[array[i]-min]-1 索引位置
            //将counts[array[i]-min] 减掉一个
            newArray[--counts[array[i]/div%10]] = array[i];
        }
        //将有序数组覆盖回array
        for (int i = 0; i < newArray.length; i++) {
            array[i] = newArray[i];
        }


    }
}
